home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 4 / Amiga Tools 4.iso / tools / dfue / term 4.6(?) / extras / source / term-source.lha / QuickSort.a < prev    next >
Encoding:
Text File  |  1996-03-18  |  3.1 KB  |  179 lines
  1. ***
  2. *
  3. *    A replacement for Lattice's qsort
  4. *
  5. *    This one is a stack miser and is (hopefully) faster.
  6. *
  7. *    The algorithm is taken from:
  8. *
  9. *    Stubbs, Webre, "Data Structures with Abstract
  10. *    Data Types and Pascal" (Pacific Grove: Brooks/Cole Pub. Co
  11. *    p. 256.
  12. *
  13. *    Modifications:
  14. *
  15. *    Middle element of array is used as partition element.
  16. *    Additional logic is provided for tail recursion optimization:
  17. *    Recursive calls sort arrays at most half the size of the array
  18. *    sorted during the previous recursive call -> little stack use.
  19. *
  20. ***
  21.  
  22.     section    text,code
  23.  
  24.     xdef    qsort
  25.     xdef    QuickSort
  26.  
  27. qsort:
  28. QuickSort:
  29.     movem.l D5/D4/D6/D7/A3,-(SP)
  30.     move.l    36(SP),A3
  31.     move.l    32(SP),D7
  32.     move.l    28(SP),D4    ; number of elements in array
  33.     move.l    24(SP),D5    ; bottom of array
  34.  
  35.     ; calculate size of array
  36.  
  37.     move.l    D4,D1        ; low word in right
  38.     swap    D1        ; high word in D1
  39.     mulu    D7,D4
  40.     mulu    D7,D1        ; multiply
  41.     swap    D1        ; shift high portion
  42.     clr.w    D1        ; mask high bits
  43.     add.l    D1,D4        ; add partials
  44.     sub.l    D7,D4        ; back up one
  45.     add.l    D5,D4        ; make into address
  46.  
  47.     ; calculate bit position to find middle
  48.  
  49.     moveq    #-1,D6
  50. cb0:
  51.     addq.l    #1,D6
  52.     btst    D6,D7
  53.     beq.b    cb0
  54.  
  55.     bsr.b    quick2
  56.  
  57.     movem.l (SP)+,D5/D4/D6/D7/A3
  58.     rts
  59.  
  60.     ;
  61.     ; exchange contents of A0, A1
  62.     ;
  63.  
  64. exch:
  65.     move.l    D7,D1
  66.     bra.s    ex1
  67. ex2:
  68.     move.b    (A0),D0
  69.     move.b    (A1),(A0)+
  70.     move.b    D0,(A1)+
  71. ex1:
  72.     dbra    D1,ex2
  73.     rts
  74.  
  75.     ; in: D5, right
  76.  
  77. quick2: movem.l D3/D2,-(SP)
  78.  
  79. quick2nr:
  80.     cmp.l    D5,D4
  81.     bls    q1        ; if left < right
  82.  
  83.     ; At this point, we wish to find middle of array
  84.     ; w/o multiplying or dividing.
  85.  
  86.     ; After finding size of array, in bytes,
  87.     ; we test hbit.     This bit will be set if we
  88.     ; are halfway between elements.
  89.  
  90.     move.l    D4,D1
  91.     sub.l    D5,D1        ; calculate size of array
  92.     btst    D6,D1
  93.     beq.s    q3
  94.     sub.l    D7,D1
  95. q3:
  96.     lsr.l    #1,D1        ; swap(d[left], d[mid]);
  97.     add.l    D5,D1
  98.  
  99.     move.l    D1,A0
  100.     move.l    D5,A1
  101.     bsr.b    exch
  102.  
  103.     move.l    D4,-(SP)
  104.     move.l    D5,-(SP)
  105.     jsr    (A3)
  106.     addq.l    #8,SP
  107.     tst.l    D0
  108.     ble.s    q2        ; if d[left] > d[right]
  109.  
  110.     move.l    D5,A0
  111.     move.l    D4,A1
  112.     bsr.b    exch        ; swap(d[left], d[right]);
  113. q2:
  114.     move.l    D5,D3        ; j := left
  115.     move.l    D4,D2        ; k := right
  116. q4:                ; repeat
  117.     add.l    D7,D3        ;  j := j + 1
  118.     move.l    D5,-(SP)
  119.     move.l    D3,-(SP)
  120.     jsr    (A3)
  121.     addq.l    #8,SP
  122.     tst.l    D0        ; until d[j] >= d[left]
  123.     blt.b    q4
  124. q5:
  125.     sub.l    D7,D2        ; k := k - 1
  126.     move.l    D5,-(SP)
  127.     move.l    D2,-(SP)
  128.     jsr    (A3)
  129.     addq.l    #8,SP
  130.     tst.l    D0        ; until d[k] <= d[left]
  131.     bgt.b    q5
  132.  
  133.     cmp.l    D3,D2
  134.     bls.s    q6        ; if j < k
  135.     move.l    D2,A1
  136.     move.l    D3,A0
  137.     bsr.b    exch        ; swap(d[j], d[k])
  138. q6:
  139.     cmp.l    D3,D2
  140.     bcc.b    q4        ; until j > k
  141.  
  142.     move.l    D2,A1
  143.     move.l    D5,A0
  144.     bsr.b    exch        ; swap(d[left], d[k])
  145.  
  146.     ; this is the recursive part.  Calculate sizes of
  147.     ; recursive calls to ensure smaller array is done
  148.     ; recursively and larger non-recursively.
  149.  
  150.     move.l    D2,D3
  151.     sub.l    D7,D2        ; k - 1
  152.     add.l    D7,D3        ; k + 1
  153.  
  154.     move.l    D2,D0
  155.     sub.l    D5,D0        ; (k - 1) - left
  156.     move.l    D4,D1
  157.     sub.l    D3,D1        ; right - (k + 1)
  158.     cmp.l    D0,D1
  159.     bge.s    q7
  160.  
  161.     move.l    D5,-(SP)
  162.     move.l    D3,D5
  163.     bsr.b    quick2        ; quick2(k + 1, right)
  164.     move.l    (SP)+,D5
  165.     move.l    D2,D4
  166.     bra.b    quick2nr    ; quick2(left, k - 1)
  167. q7:
  168.     move.l    D4,-(SP)
  169.     move.l    D2,D4
  170.     bsr    quick2        ; quick2(left, k - 1)
  171.     move.l    (SP)+,D4
  172.     move.l    D3,D5
  173.     bra    quick2nr    ; quick2(k + 1, right)
  174. q1:
  175.     movem.l (SP)+,D3/D2
  176.     rts
  177.  
  178.     end
  179.